// 文件名：list_undo_redo.cpp
// 目的：用 std::list 与“游标迭代器”实现一个简单的撤销/重做（undo/redo）历史。
// 模型：
//   - states_：按时间顺序存储状态；
//   - cursor_：指向“当前状态”；
// 操作：
//   - apply(state)：应用新状态时，丢弃 cursor_ 之后的“未来历史”，插入新状态并移动到该状态；
//   - undo()：若可撤销，cursor_ 向前移动一格；
//   - redo()：若可重做，cursor_ 向后移动一格；
//   - current()：返回当前状态引用。
// 不变式：cursor_ 总是合法地指向 states_ 中的某元素。
// 复杂度：
//   - apply：O(k) 擦除尾部（k=被丢弃历史数） + O(1) 插入；
//   - undo/redo：O(1)。

#include <list>
#include <string>
#include <iostream>

class History {
public:
    // 应用新状态：丢弃未来，插入到当前之后，并将游标移至新状态
    void apply(std::string state) {
        // 当有新状态时，丢弃当前光标之后的历史
        states_.erase(std::next(cursor_), states_.end());
        // 在 cursor_ 之后插入新状态，cursor_ 指向新插入的元素
        cursor_ = states_.insert(std::next(cursor_), std::move(state));
    }

    // 撤销：将 cursor_ 向前移动（若已在起点则失败）
    bool undo() {
        if (cursor_ == states_.begin()) return false;
        --cursor_;
        return true;
    }

    // 重做：将 cursor_ 向后移动（若已在末尾则失败）
    bool redo() {
        if (std::next(cursor_) == states_.end()) return false;
        ++cursor_;
        return true;
    }

    // 获取当前状态
    const std::string& current() const {
        return *cursor_;
    }

    // 初始化：创建一个初始状态，并将 cursor_ 指向它
    History() {
        cursor_ = states_.insert(states_.end(), "initial");
    }

private:
    std::list<std::string> states_;                 // 历史状态序列
    std::list<std::string>::iterator cursor_;       // 当前状态游标
};

int main() {
    History history;
    std::cout << "Current: " << history.current() << '\n';

    history.apply("draw line");
    history.apply("fill color");
    std::cout << "Current: " << history.current() << '\n';

    history.undo();
    std::cout << "After undo: " << history.current() << '\n';

    history.redo();
    std::cout << "After redo: " << history.current() << '\n';

    history.apply("add text"); // 重做链断开
    if (!history.redo()) {
        std::cout << "Redo unavailable after branching\n";
    }
    std::cout << "Current: " << history.current() << '\n';
    return 0;
}